/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhong
 *
 */
public class AllPossibleFullBinaryTrees {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	HashMap<Integer, List<TreeNode>> memo = new HashMap<>();

	public List<TreeNode> allPossibleFBT(int N) {
		if (memo.containsKey(N)) {
			return memo.get(N);
		}
		if (N == 1 && !memo.containsKey(1)) {
			TreeNode root = new TreeNode(0);
			List<TreeNode> roots = new ArrayList<>();
			roots.add(root);
			memo.put(1, roots);
			return roots;
		}
		List<TreeNode> roots = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			List<TreeNode> lefts = allPossibleFBT(i);
			List<TreeNode> rights = allPossibleFBT(N - i - 1);
			for (TreeNode left : lefts) {
				for (TreeNode right : rights) {
					TreeNode root = new TreeNode(0);
					root.left = left;
					root.right = right;
					roots.add(root);
				}
			}
		}
		memo.put(N, roots);
		return roots;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new AllPossibleFullBinaryTrees().allPossibleFBT(7).size());
		;
	}

}
